package edu.cmu.cs211.pg.internal;

import static org.junit.Assert.assertEquals;

import java.util.Collection;
import java.util.HashSet;

import org.junit.Test;

import edu.cmu.cs211.pg.algorithms.Dijkstra;
import edu.cmu.cs211.pg.graph.Edge;
import edu.cmu.cs211.pg.graph.MyDirectedGraph;
import edu.cmu.cs211.pg.graph.Path;
import edu.cmu.cs211.pg.graph.WeightedEdge;

public class DijkstraTest {
	
	/*
	 * negativeWeight tests check for negative edge errors in dijkstra 
	 */
	
	@Test(expected = IllegalArgumentException.class)
	public void NegativeWeightExceptionTest() throws IllegalArgumentException{
		HashSet<Integer> hs = new HashSet<Integer>();
		Integer i = 1;
		Integer i2 = 2;
		Integer i3 = 3;
		hs.add(1);
		hs.add(2);
		hs.add(3);
		
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		WeightedEdge e = new WeightedEdge(1, 2, 4);
		WeightedEdge e2 = new WeightedEdge(1, 3, 6);
		WeightedEdge e3 = new WeightedEdge(2, 3, -1);
		WeightedEdge e4 = new WeightedEdge(3, 4, 1);
		edges.add(e);
		edges.add(e2);
		edges.add(e3);
		
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		
		Dijkstra d = new Dijkstra();
		//Path path = d.shortestPath(g, 1, 4);
		assertEquals(new IllegalArgumentException(), d.shortestPath(g, (Integer) e.src(), (Integer) e4.dest()));

	}
	
	@Test(expected = IllegalArgumentException.class)
	public void NegativeEdgeWeight2() {
		HashSet<Integer> hs = new HashSet<Integer>();
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		Dijkstra d = new Dijkstra();
		
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		hs.add(5);
		hs.add(6);
		
		edges.add(new WeightedEdge(2,1,1));
		edges.add(new WeightedEdge(3,1,1));
		edges.add(new WeightedEdge(4,1,1));
		edges.add(new WeightedEdge(5,6,-1));
		
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		Path path = d.shortestPath(g, 1, 4);
		assertEquals(null, path);
	}
	
	

	/*
	 * just a simple small test to see if dijkstra works
	 */
	@Test
	public void SimpleDijkstraTest() {
		HashSet<Integer> hs = new HashSet<Integer>();
		Integer i = 1;
		Integer i2 = 2;
		Integer i3 = 3;
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		WeightedEdge e = new WeightedEdge(1, 2, 4);
		WeightedEdge e2 = new WeightedEdge(1, 3, 6);
		WeightedEdge e3 = new WeightedEdge(2, 3, 1);
		WeightedEdge e4 = new WeightedEdge(3, 4, 1);
		edges.add(e);
		edges.add(e2);
		edges.add(e3);
	
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		
		Dijkstra d = new Dijkstra();
		Path path = d.shortestPath(g, (Integer) e.src(), (Integer) e3.dest());
		//System.out.println(path.toString());
		assertEquals(5, path.pathWeight());
		

	}
	
	/*
	 * makes a linear graph with a single outgoing edge from each node
	 * to the next and tests to see if dijkstra can handle it
	 */
	@Test public void LinearGraphTest() {
		HashSet<Integer> hs = new HashSet<Integer>();
		hs.add(0);
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		WeightedEdge we = new WeightedEdge(0,1,1);
		WeightedEdge we2 = new WeightedEdge(1,2,1);
		WeightedEdge we3 = new WeightedEdge(2,3,1);
		WeightedEdge we4 = new WeightedEdge(3,4,1);
		edges.add(we);
		edges.add(we2);
		edges.add(we3);
		edges.add(we4);
		
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		Dijkstra d = new Dijkstra();
		Path path = d.shortestPath(g, 0, 4);
		assertEquals(path.pathWeight(), 4);
	}
	
	/*
	 * tests dijkstra using different disconnected graphs
	 */
	@Test public void DisconnectedGraphTest() {
		HashSet<Integer> hs = new HashSet<Integer>();
		Integer i = 1;
		Integer i2 = 2;
		Integer i3 = 3;
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		hs.add(5);
		hs.add(6);
		hs.add(7);
		
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		WeightedEdge e = new WeightedEdge(1, 2, 4);
		WeightedEdge e2 = new WeightedEdge(1, 3, 6);
		WeightedEdge e3 = new WeightedEdge(2, 3, 1);
		WeightedEdge e4 = new WeightedEdge(3, 4, 1);
		WeightedEdge e5 = new WeightedEdge(5, 6, 3);
		WeightedEdge e6 = new WeightedEdge(5, 7, 1);
		WeightedEdge e7 = new WeightedEdge(6, 7, 2);
		edges.add(e);
		edges.add(e2);
		edges.add(e3);
	
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		
		Dijkstra d = new Dijkstra();
		Path path = d.shortestPath(g, (Integer) e.src(), (Integer) e6.dest());
		//System.out.println(path.toString());
		assertEquals(null, path);
	}
	
	/*
	 * checks to see how dijkstra responds to cycles
	 */
	@Test public void CycleTest() {
		HashSet<Integer> hs = new HashSet<Integer>();
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		hs.add(5);
		hs.add(6);
		hs.add(7);
		
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		WeightedEdge e = new WeightedEdge(1, 2, 4);
		WeightedEdge e2 = new WeightedEdge(2, 3, 1);
		WeightedEdge e3 = new WeightedEdge(3, 4, 3);
		WeightedEdge e4 = new WeightedEdge(3, 1, 2);
		WeightedEdge e5 = new WeightedEdge(1, 4, 1);
		WeightedEdge e6 = new WeightedEdge(4, 1, 2);
		WeightedEdge e7 = new WeightedEdge(4, 3, 1);
		
		edges.add(e);
		edges.add(e2);
		edges.add(e3);
		edges.add(e4);
		edges.add(e5);
		edges.add(e6);
		edges.add(e7);
	
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		
		Dijkstra d = new Dijkstra();
		Path path = d.shortestPath(g, (Integer) e.src(), (Integer) e2.dest());
		//System.out.println(path.toString());
		assertEquals(2, path.pathWeight());
	}
	
	/*
	 * another disconnected test
	 */
	@Test
	public void DisconnectedTest2() {
		HashSet<Integer> hs = new HashSet<Integer>();
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		Dijkstra d = new Dijkstra();
		
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		Path path = d.shortestPath(g, 1, 4);
		assertEquals(null, path);
	}
	
	@Test 
	public void DisconnectedTest3() {
		HashSet<Integer> hs = new HashSet<Integer>();
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		Dijkstra d = new Dijkstra();
		
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		hs.add(5);
		hs.add(6);
		
		edges.add(new WeightedEdge(1,2,3));
		edges.add(new WeightedEdge(3,4,1));
		edges.add(new WeightedEdge(5,6,1));
		
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		Path path = d.shortestPath(g, 1, 6);
		assertEquals(null, path);
	}
	
	@Test 
	public void DisconnectedTest4() {
		HashSet<Integer> hs = new HashSet<Integer>();
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		Dijkstra d = new Dijkstra();
		
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		hs.add(5);
		hs.add(6);
		hs.add(7);
		
		edges.add(new WeightedEdge(1,2,3));
		edges.add(new WeightedEdge(2,3,2));
		edges.add(new WeightedEdge(3,4,1));
		edges.add(new WeightedEdge(4,5,3));
		edges.add(new WeightedEdge(5,6,1));
		edges.add(new WeightedEdge(7,1,1));
		
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		Path path = d.shortestPath(g, 1, 7);
		assertEquals(null, path);
	}
	
	/*
	 * a more elaborate linear graph test
	 */
	@Test
	public void LinearGraphTest2() {
		HashSet<Integer> hs = new HashSet<Integer>();
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		Dijkstra d = new Dijkstra();
		
		for(int i = 0; i <= 50; i++) {
			hs.add(i);
		}
		
		for(int i = 0; i < 49; i++) {
			edges.add(new WeightedEdge(i, i+1, 1));
		}
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		Path path = d.shortestPath(g, 0, 50);
		assertEquals(1000, path.pathWeight());
	}
	
	@Test
	public void DisconnectedTest5() {
		HashSet<Integer> hs = new HashSet<Integer>();
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		Dijkstra d = new Dijkstra();
		
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		
		edges.add(new WeightedEdge(2,1,1));
		edges.add(new WeightedEdge(3,1,1));
		edges.add(new WeightedEdge(4,1,1));
		
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		Path path = d.shortestPath(g, 1, 4);
		assertEquals(null, path);
	}

	@Test(expected = IllegalArgumentException.class)
	public void GraphTest() {
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = null;
		Dijkstra d = new Dijkstra();
		
		Path path = d.shortestPath(g, 1, 4);
		assertEquals(null, path);
		
	}
	
	/*
	 * checks to see what happens when pass in a null graph
	 */
	@Test
	public void nullTest(){
		HashSet<Integer> hs = new HashSet<Integer>();
		HashSet<WeightedEdge<Integer>> edges = new HashSet<WeightedEdge<Integer>>();
		Dijkstra d = new Dijkstra();
		
		hs.add(1);
		hs.add(2);
		hs.add(3);
		hs.add(4);
		hs.add(5);
		hs.add(6);
		hs.add(7);
		
		edges.add(new WeightedEdge(1,2,3));
		edges.add(new WeightedEdge(2,3,2));
		//edges.add(new WeightedEdge(3,4,null));
		edges.add(new WeightedEdge(4,5,3));
		edges.add(new WeightedEdge(5,6,1));
		edges.add(new WeightedEdge(7,1,1));
		
		MyDirectedGraph<Integer, WeightedEdge<Integer>> g = new MyDirectedGraph(hs, edges);
		
		Path path = d.shortestPath(g, 1, 7);
		assertEquals(null, path);
	}
}
